Integer Sequences on:
[Wikipedia]
[Google]
[Amazon]
In
Journal of Integer Sequences
Articles are freely available online. {{Series (mathematics) Arithmetic functions
In mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, an integer sequence is a sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
(i.e., an ordered list) of integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s.
An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For example, the sequence 0, 1, 1, 2, 3, 5, 8, 13, ... (the Fibonacci sequence
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
) is formed by starting with 0 and 1 and then adding any two consecutive terms to obtain the next one: an implicit description. The sequence 0, 3, 8, 15, ... is formed according to the formula ''n''2 − 1 for the ''n''th term: an explicit definition.
Alternatively, an integer sequence may be defined by a property which members of the sequence possess and other integers do not possess. For example, we can determine whether a given integer is a perfect number
In number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number.
T ...
, even though we do not have a formula for the ''n''th perfect number.
Examples
Integer sequences that have their own name include: *Abundant number
In number theory, an abundant number or excessive number is a number for which the sum of its proper divisors is greater than the number. The integer 12 is the first abundant number. Its proper divisors are 1, 2, 3, 4 and 6 for a total of 16. Th ...
s
*Baum–Sweet sequence
In mathematics the Baum–Sweet sequence is an infinite automatic sequence of 0s and 1s defined by the rule:
:''b'n'' = 1 if the binary representation of ''n'' contains no block of consecutive 0s of odd length;
:''b'n'' = 0 otherwise;
for ...
*Bell number
In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy ...
s
* Binomial coefficients
*Carmichael number
In number theory, a Carmichael number is a composite number n, which in modular arithmetic satisfies the congruence relation:
:b^n\equiv b\pmod
for all integers b. The relation may also be expressed in the form:
:b^\equiv 1\pmod.
for all integers ...
s
*Catalan number
In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Ca ...
s
*Composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
s
*Deficient number
In number theory, a deficient number or defective number is a number ''n'' for which the sum of divisors of ''n'' is less than 2''n''. Equivalently, it is a number for which the sum of proper divisors (or aliquot sum) is less than ''n''. For ex ...
s
*Euler number
In mathematics, the Euler numbers are a sequence ''En'' of integers defined by the Taylor series expansion
:\frac = \frac = \sum_^\infty \frac \cdot t^n,
where \cosh (t) is the hyperbolic cosine function. The Euler numbers are related to a ...
s
* Even and odd numbers
* Factorial numbers
*Fibonacci number
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
s
*Fibonacci word
A Fibonacci word is a specific sequence of binary digits (or symbols from any two-letter alphabet). The Fibonacci word is formed by repeated concatenation in the same way that the Fibonacci numbers are formed by repeated addition.
It is a para ...
*Figurate numbers
The term figurate number is used by different writers for members of different sets of numbers, generalizing from triangular numbers to different shapes (polygonal numbers) and different dimensions (polyhedral numbers). The term can mean
* polygo ...
*Golomb sequence In mathematics, the Golomb sequence, named after Solomon W. Golomb (but also called Silverman's sequence), is a monotonically increasing integer sequence where ''an'' is the number of times that ''n'' occurs in the sequence, starting with ''a''1 = ...
*Happy number
In number theory, a happy number is a number which eventually reaches 1 when replaced by the sum of the square of each digit. For instance, 13 is a happy number because 1^2+3^2=10, and 1^2+0^2=1. On the other hand, 4 is not a happy number because ...
s
*Highly composite number
__FORCETOC__
A highly composite number is a positive integer with more divisors than any smaller positive integer has. The related concept of largely composite number refers to a positive integer which has at least as many divisors as any smaller ...
s
* Highly totient numbers
*Home prime In number theory, the home prime HP(''n'') of an integer ''n'' greater than 1 is the prime number obtained by repeatedly factoring the increasing concatenation of prime factors including repetitions. The ''m''th intermediate stage in the process o ...
s
*Hyperperfect number In mathematics, a ''k''-hyperperfect number is a natural number ''n'' for which the equality ''n'' = 1 + ''k''(''σ''(''n'') − ''n'' − 1) holds, where ''σ''(''n'') is the divisor function (i.e., the sum of all positive divisors of ''n ...
s
*Juggler sequence
In number theory, a juggler sequence is an integer sequence that starts with a positive integer ''a''0, with each subsequent term in the sequence defined by the recurrence relation:
a_= \begin
\left \lfloor a_k^ \right \rfloor, & \text a_k \text ...
*Kolakoski sequence
In mathematics, the Kolakoski sequence, sometimes also known as the Oldenburger–Kolakoski sequence, is an infinite sequence of symbols that is the sequence of run lengths in its own run-length encoding. It is named after the recreational mathe ...
*Lucky number
In number theory, a lucky number is a natural number in a set which is generated by a certain "sieve". This sieve is similar to the Sieve of Eratosthenes that generates the primes, but it eliminates numbers based on their position in the remain ...
s
*Lucas number
The Lucas numbers or Lucas series are an integer sequence named after the mathematician François Édouard Anatole Lucas (1842–1891), who studied both that sequence and the closely related Fibonacci numbers. Lucas numbers and Fibonacci n ...
s
*Motzkin number
In mathematics, the th Motzkin number is the number of different ways of drawing non-intersecting chords between points on a circle (not necessarily touching every point by a chord). The Motzkin numbers are named after Theodore Motzkin and have d ...
s
*Natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s
*Padovan number
In number theory, the Padovan sequence is the sequence of integers ''P''(''n'') defined. by the initial values
:P(0)=P(1)=P(2)=1,
and the recurrence relation
:P(n)=P(n-2)+P(n-3).
The first few values of ''P''(''n'') are
:1, 1, 1, 2, 2, 3, 4, 5 ...
s
*Partition number
In number theory, the partition function represents the number of possible partitions of a non-negative integer . For instance, because the integer 4 has the five partitions , , , , and .
No closed-form expression for the partition function is ...
s
*Perfect number
In number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number.
T ...
s
*Prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s
*Pseudoprime
A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy.
Some sources use the term pseudoprime to ...
numbers
*Recamán's sequence In mathematics and computer science, Recamán's sequence is a well known sequence defined by a recurrence relation. Because its elements are related to the previous elements in a straightforward way, they are often defined using recursion.
It tak ...
*Regular paperfolding sequence In mathematics the regular paperfolding sequence, also known as the dragon curve sequence, is an infinite sequence of 0s and 1s. It is obtained from the repeating partial sequence
by filling in the question marks by another copy of the whole sequen ...
*Rudin–Shapiro sequence In mathematics, the Rudin–Shapiro sequence, also known as the Golay–Rudin–Shapiro sequence, is an infinite 2- automatic sequence named after Marcel Golay, Walter Rudin, and Harold S. Shapiro, who independently investigated its properties.
...
*Semiperfect number
In number theory, a semiperfect number or pseudoperfect number is a natural number ''n'' that is equal to the sum of all or some of its proper divisors. A semiperfect number that is equal to the sum of all its proper divisors is a perfect number.
...
s
*Semiprime
In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers.
Because there are infinitely many prime nu ...
numbers
* Superperfect numbers
*Thue–Morse sequence
In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is the binary sequence (an infinite sequence of 0s and 1s) obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus ...
*Ulam numbers
In mathematics, the Ulam numbers comprise an integer sequence devised by and named after Stanislaw Ulam, who introduced it in 1964. The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with ''U''1 = 1 and ''U''2 =&n ...
*Weird number
In number theory, a weird number is a natural number that is abundant but not semiperfect.
In other words, the sum of the proper divisors (divisors including 1 but not itself) of the number is greater than the number, but no subset of those divis ...
s
* Wolstenholme number
Computable and definable sequences
An integer sequence is acomputable
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...
sequence if there exists an algorithm which, given ''n'', calculates ''a''''n'', for all ''n'' > 0. The set of computable integer sequences is countable
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...
. The set of all integer sequences is uncountable
In mathematics, an uncountable set (or uncountably infinite set) is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal num ...
(with cardinality equal to that of the continuum), and so not all integer sequences are computable.
Although some integer sequences have definitions, there is no systematic way to define what it means for an integer sequence to be definable in the universe or in any absolute (model independent) sense.
Suppose the set ''M'' is a transitive model In mathematical set theory, a transitive model is a model of set theory that is standard and transitive. Standard means that the membership relation is the usual one, and transitive means that the model is a transitive set or class.
Examples
*An ...
of ZFC set theory. The transitivity of M implies that the integers and integer sequences inside M are actually integers and sequences of integers. An integer sequence is a definable sequence relative to ''M'' if there exists some formula ''P''(''x'') in the language of set theory, with one free variable and no parameters, which is true in ''M'' for that integer sequence and false in ''M'' for all other integer sequences. In each such ''M'', there are definable integer sequences that are not computable, such as sequences that encode the Turing jump
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine w ...
s of computable sets.
For some transitive models ''M'' of ZFC, every sequence of integers in ''M'' is definable relative to ''M''; for others, only some integer sequences are (Hamkins et al. 2013). There is no systematic way to define in ''M'' itself the set of sequences definable relative to ''M'' and that set may not even exist in some such ''M''. Similarly, the map from the set of formulas that define integer sequences in ''M'' to the integer sequences they define is not definable in ''M'' and may not exist in ''M''. However, in any model that does possess such a definability map, some integer sequences in the model will not be definable relative to the model (Hamkins et al. 2013).
If ''M'' contains all integer sequences, then the set of integer sequences definable in ''M'' will exist in ''M'' and be countable and countable in ''M''.
Complete sequences
A sequence of positive integers is called acomplete sequence In mathematics, a sequence of natural numbers is called a complete sequence if every positive integer can be expressed as a sum of values in the sequence, using each value at most once.
For example, the sequence of powers of two (1, 2, 4, 8, ...) ...
if every positive integer can be expressed as a sum of values in the sequence, using each value at most once.
See also
*On-Line Encyclopedia of Integer Sequences
The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to t ...
** List of OEIS sequences
References
* .External links
Journal of Integer Sequences
Articles are freely available online. {{Series (mathematics) Arithmetic functions